P10867 [HBCPC2024] Points on the Number Axis A 题解
0x00 题目翻译
最初数轴上由 $n$ 个点 $x_1,x_2,x_3,\dots,x_n$，每次随机取两个，把它们拿走后再把它们的平均数 $\dfrac{x_i+x_j}{2}$ 放回数轴，最后剩下一个点，求这个点坐标的期望。
0x01 解题思路
1. 猜想结论
$$ans_n=\dfrac{\sum_{i=1}^{n}a_i}{n}$$
2. proof
3.对输出的处理
要求输出 $p\times q^{-1}$，这里我们需要用乘法逆元。
显而易见 $998244353$ 是质数，乘法逆元可以通过 $q^{998244353-2}$ 得到，需要快速幂。
0x02 AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int p=998244353;
int fpow(int n,int k){
if(k==1){
return n;
}
else if(k==0){
return 1;
}
long long ans=1;
while(k) {
if(k&1)
ans=ans*n%p;
n=n*n%p;
k>>=1;
}
return ans;
}
int inv(int n){
return fpow(n,p-2);
}
void solve(){
int n,s=0;
cin>>n;
for(int i=1;i<=n;i++){
int t;
cin>>t;
s+=t;
s%=p;
}
for(int i=2;i*i<=max(n,s)&&i<=min(n,s);i++){
if(n%i==0&&s%i==0){
n/=i,s/=i;
}
}
cout<<inv(n)*s%p<<endl;
}
signed main(){
int t;
t=1;
while(t--){
solve();
}
return 0;
}
|